package Day2025_02_28;

public class LeetCodeLCR170 {
    public int ret = 0;
    public int reversePairs(int[] record) {
        mergeSort(record, 0 , record.length - 1);
        return ret;
    }
    private void mergeSort (int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = (right + left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }
    private void merge (int[] nums, int left, int right, int mid) {
        int s1 = left, e1 = mid;
        int s2 = mid + 1, e2 = right;
        int k = 0;
        int[] tmpArr = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] <= nums[s2]) tmpArr[k++] = nums[s1++];
            else {
                tmpArr[k++] = nums[s2++];
                ret += e1 - s1 + 1;
            }
        }
        while (s1 <= e1) tmpArr[k++] = nums[s1++];
        while (s2 <= e2) tmpArr[k++] = nums[s2++];
        for (int i = 0; i < tmpArr.length; i++) nums[left + i] = tmpArr[i];
    }
}
